package personal.leil.learning.undigraph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author Leil
 * @version 1.0
 * @since 2024/1/22
 */
public class Undigraph {

    /**
     * all vertices of Graph
     */
    public HashSet<Vertex> vertices;

    /**
     * all edges of Graph
     */
    public HashSet<EdgeUndirected> edges;

    public Undigraph() {
        this.vertices = new HashSet<>();
        this.edges = new HashSet<>();
    }

    /**
     * add vertex to Graph
     *
     * @param vertex vertex for adding
     */
    public void addVertex(Vertex vertex) {
        vertices.add(vertex);
    }

    /**
     * add edge to Graph
     *
     * @param edge edge for adding
     */
    public void addEdge(EdgeUndirected edge) {
        edges.add(edge);
    }

    /**
     * 深度优先遍历
     *
     * @param graph target graph
     */
    public static void dfs1(Undigraph graph) {
        HashSet<Vertex> alreadyProcess = new HashSet<>();
        for (Vertex head : graph.vertices) {
            if (alreadyProcess.contains(head)) {
                continue;
            }
            dfs1(alreadyProcess, head);
        }
    }

    private static void dfs1(HashSet<Vertex> alreadyProcess, Vertex head) {
        Stack<Vertex> stack = new Stack<>();
        stack.push(head);
        alreadyProcess.add(head);
        while (!stack.empty()) {
            Vertex vertex = stack.pop();
            System.out.println("Vertex[" + vertex.value + "]");
            for (Vertex next : vertex.neighbors) {
                if (!alreadyProcess.contains(next)) {
                    stack.push(next);
                    alreadyProcess.add(next);
                }
            }
        }
    }


    /**
     * 深度优先遍历（递归压栈的方式实现）
     *
     * @param graph target graph
     */
    public static void dfs2(Undigraph graph) {
        HashSet<Vertex> alreadyProcess = new HashSet<>();
        for (Vertex head : graph.vertices) {
            if (alreadyProcess.contains(head)) {
                continue;
            }
            alreadyProcess.add(head);
            dfsRecursion(head, alreadyProcess);
        }
    }

    public static void dfsRecursion(Vertex vertex, HashSet<Vertex> alreadyProcess) {
        System.out.println("Vertex[" + vertex.value + "]");
        for (Vertex next : vertex.neighbors) {
            if (!alreadyProcess.contains(next)) {
                alreadyProcess.add(next);
                dfsRecursion(next, alreadyProcess);
            }
        }
    }


    /**
     * 广度优先遍历
     *
     * @param graph target graph
     */
    public static void bfs(Undigraph graph) {
        HashSet<Vertex> alreadyProcess = new HashSet<>();
        Queue<Vertex> queue = new LinkedList<>();
        if (graph.vertices.size() < 1) {
            return;
        }
        for (Vertex head : graph.vertices) {
            if (alreadyProcess.contains(head)) {
                continue;
            }
            queue.offer(head);
            alreadyProcess.add(head);
            while (queue.size() != 0) {
                Vertex vertex = queue.poll();
                System.out.println("Vertex[" + vertex.value + "]");
                for (Vertex next : vertex.neighbors) {
                    if (!alreadyProcess.contains(next)) {
                        queue.offer(next);
                        alreadyProcess.add(next);
                    }
                }
            }
        }
    }


    /**
     * print graph whit description
     *
     * @param graph target graph
     */
    public static void printGraph(Undigraph graph) {
        for (Vertex vertex : graph.vertices) {
            System.out.print("Vertex " + vertex.value + " is connected to: ");
            for (Vertex neighbor : vertex.neighbors) {
                System.out.print(neighbor.value + " ");
            }
            System.out.println();
        }
    }

    /**
     * 邻接矩阵示例
     *
     * @param graph target graph
     */
    private static void printAdjacencyMatrix(Undigraph graph) {
        int size = graph.vertices.size();
        int[][] adjacencyMatrix = new int[size][size];

        for (Vertex vertex : graph.vertices) {
            for (Vertex neighbor : vertex.neighbors) {
                adjacencyMatrix[vertex.value - 1][neighbor.value - 1] = 1;
                adjacencyMatrix[neighbor.value - 1][vertex.value - 1] = 1;
            }
        }

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用Graphviz可视化图
     *
     * @param graph target graph
     */
    private static void visualizeGraphWithGraphviz(Undigraph graph) {
        StringBuilder dotCode = new StringBuilder("graph G {\n");
        for (Vertex vertex : graph.vertices) {
            dotCode.append("  ").append(vertex.value).append(";\n");
            for (Vertex neighbor : vertex.neighbors) {
                dotCode.append("  ").append(vertex.value).append(" -- ").append(neighbor.value).append(";\n");
            }
        }
        dotCode.append("}");
        System.out.println(dotCode);
        // 将dotCode写入文件，并使用Graphviz渲染
        // 可以使用在线工具或本地Graphviz软件进行渲染
    }


    /************************** For Test *******************************/
    public static void main(String[] args) {
        // 创建图
        Undigraph graph = new Undigraph();

        // 创建顶点
        Vertex v1 = new Vertex(1);
        Vertex v2 = new Vertex(2);
        Vertex v3 = new Vertex(3);
        Vertex v4 = new Vertex(4);
        Vertex v5 = new Vertex(5);
        Vertex v6 = new Vertex(6);
        Vertex v7 = new Vertex(7);
        Vertex v8 = new Vertex(8);
        Vertex v9 = new Vertex(9);
        Vertex v10 = new Vertex(10);
        Vertex v11 = new Vertex(11);
        Vertex v12 = new Vertex(12);

        // 添加顶点到图中
        graph.addVertex(v1);
        graph.addVertex(v2);
        graph.addVertex(v3);
        graph.addVertex(v4);
        graph.addVertex(v5);
        graph.addVertex(v6);
        graph.addVertex(v7);
        graph.addVertex(v8);
        graph.addVertex(v9);
        graph.addVertex(v10);
        graph.addVertex(v11);
        graph.addVertex(v12);

        // 添加边（连接顶点）
        v1.addNeighbor(v2);
        v2.addNeighbor(v3);
        v2.addNeighbor(v4);
        v2.addNeighbor(v5);
        v5.addNeighbor(v6);
        v6.addNeighbor(v7);
        v2.addNeighbor(v8);
        v8.addNeighbor(v9);
        v8.addNeighbor(v10);
        v7.addNeighbor(v11);
        v6.addNeighbor(v12);
        v11.addNeighbor(v12);

        dfs1(graph);
        System.out.println("==================");
        dfs2(graph);
        System.out.println("==================");
        bfs(graph);
        // 打印图的结构
//        printGraph(graph);
//        printAdjacencyMatrix(graph);
        visualizeGraphWithGraphviz(graph);
    }


}
